<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.1.0">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.0.0/css/all.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.css">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/themes/green/pace-theme-minimal.css">
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pace/1.2.4/pace.min.js" integrity="sha256-gqd7YTjg/BtfqWSwsJOvndl0Bxc8gFImLEkXQT8+qj0=" crossorigin="anonymous"></script>

<script class="next-config" data-name="main" type="application/json">{"hostname":"liukairui.me","root":"/","images":"/images","scheme":"Muse","darkmode":false,"version":"8.10.1","exturl":false,"sidebar":{"position":"left","display":"hide","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":true,"pangu":true,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":false,"nav":null,"activeClass":"valine"},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta name="description" content="原题来自2020牛客寒假算法基础集训营1，作以存档备查">
<meta property="og:type" content="article">
<meta property="og:title" content="2020牛客寒假算法基础集训营1题解">
<meta property="og:url" content="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/">
<meta property="og:site_name" content="LiuKairui Website">
<meta property="og:description" content="原题来自2020牛客寒假算法基础集训营1，作以存档备查">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-10-30T16:00:02.000Z">
<meta property="article:modified_time" content="2021-10-18T06:44:13.585Z">
<meta property="article:author" content="Liu Kairui">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="牛客">
<meta property="article:tag" content="ACM">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/","path":"article/2020牛客寒假算法基础集训营1题解/","title":"2020牛客寒假算法基础集训营1题解"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>2020牛客寒假算法基础集训营1题解 | LiuKairui Website</title>
  

  <script src="/js/third-party/analytics/baidu-analytics.js"></script>
  <script async src="https://hm.baidu.com/hm.js?ea07bceb8f5fa721da2ebf01833faa32"></script>



<div class="nindexBK">
<div class="nindexBKC"></div>
<div class="nindex">
  <h1>Hey👋</h1>
  <p style="font-weight: 500; font-size: 2.2em">欢迎访问Liu Kairui的个人站.</p>
  <p>
      我是一个来自重庆的在校大学生, 偏爱于前端技术<!--与OS设计-->, 偶尔使用 JS / Go 进行轻量项目开发, 欢迎访问我的
      <a href="https://github.com/KairuiLiu" target="_blank"><i class="fab fa-github-alt"></i> GitHub</a> .
  </p>
  <p>
      这个网站主要用来存储学习 / 瞎搞的笔记, 同时提供了邮件、图床等服务. 对于一些自认为有趣的<a href="javascript:;" id="myProj">项目</a>, 我也会将项目介绍, 文档, 甚至是设计指南发布在这里.
  </p>
  <ul>
    <li><p><a href="/artrank/" target="_blank">ArtRank</a>: 基于Node.JS的PageRank文献管理推荐系统</p></li>
    <li><p><a href="/gooj/" target="_blank">GoOJ</a>: 基于Golang的高校在线评测系统</p></li>
    <li><p><a href="/projects/" target="_blank">更多 <i class="fas fa-angle-right"></i></a></p></li>

  </ul>
  <p>
      可以在这些平台找到我: 
      <a href="https://www.zhihu.com/people/liu-kai-rui-18" target="_blank">知乎</a>,
      <a href="https://space.bilibili.com/33238144" target="_blank">bilibili</a>
      和
      <a href="https://www.coolapk.com/u/805314?from=qr" target="_blank">酷安</a>.
  </p>

  <p>
      下滑即可进入博客 <i class="fas fa-arrow-down"></i>
  </p>
</div>
</div>  

 
<script>
  var OriginTitile = document.title;
  var titleTime;
  document.addEventListener("visibilitychange", function() {
    if (document.hidden) {
      document.title = "谢谢离开 | " + OriginTitile;
      clearTimeout(titleTime);
    } else {
      document.title = "欢迎归来 | " + OriginTitile;
      titleTime = setTimeout(function() {
        document.title = OriginTitile;
      }, 2000);
    }
  });
</script>


<script>
  function checkIndex(){
    let nindexItems = [[".nindexBK","display","block","none"],[".headband","display","none","block"],["div.toggle.sidebar-toggle","visibility","hidden","visible"]]; // ,["button.darkmode-toggle","visibility","hidden","visible"]];
    let isIndex = new RegExp("^(\/){0,1}(index){0,1}(\.html){0,1}(/)*$").test(location.pathname);
    let backCanvas = document.querySelector(".nindexBK");
    nindexItems.dispShift = function (stat){this.forEach((e) => {try{document.querySelector(e[0]).style[e[1]]=e[2+stat];}catch{}})}
    if(isIndex){
      nindexItems.dispShift(0);
      window.onscroll=function(){
        if(document.documentElement.scrollTop>backCanvas.offsetHeight*1.05){
          nindexItems.dispShift(1);window.onscroll=null;
        }
      }
      document.querySelector("#myProj").onclick=()=>{
        let projlist = document.querySelector(".nindex>ul");
        projlist.className.indexOf("ulactive")==-1?projlist.classList.add("ulactive"):projlist.classList.remove("ulactive")
      }
    }else nindexItems.dispShift(1);
  }
  checkIndex();
</script>

<!--<script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>-->

  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
<link rel="alternate" href="/atom.xml" title="LiuKairui Website" type="application/atom+xml">
<style>.darkmode--activated{--body-bg-color:#282828;--content-bg-color:#333;--card-bg-color:#555;--text-color:#ccc;--blockquote-color:#bbb;--link-color:#ccc;--link-hover-color:#eee;--brand-color:#ddd;--brand-hover-color:#ddd;--table-row-odd-bg-color:#282828;--table-row-hover-bg-color:#363636;--menu-item-bg-color:#555;--btn-default-bg:#222;--btn-default-color:#ccc;--btn-default-border-color:#555;--btn-default-hover-bg:#666;--btn-default-hover-color:#ccc;--btn-default-hover-border-color:#666;--highlight-background:#282b2e;--highlight-foreground:#a9b7c6;--highlight-gutter-background:#34393d;--highlight-gutter-foreground:#9ca9b6}.darkmode--activated img{opacity:.75}.darkmode--activated img:hover{opacity:.9}.darkmode--activated code{color:#69dbdc;background:0 0}button.darkmode-toggle{z-index:9999}.darkmode-ignore,img{display:flex!important}</style></head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">LiuKairui Website</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">要有信仰</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu">
        <li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li>
        <li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li>
        <li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fas fa-hashtag fa-fw"></i>标签</a></li>
        <li class="menu-item menu-item-收藏夹"><a href="/favorites/" rel="section"><i class="fab fa-gratipay fa-fw"></i>收藏夹</a></li>
        <li class="menu-item menu-item-留言板"><a href="/messageBoard/" rel="section"><i class="fab fa-facebook-messenger fa-fw"></i>留言板</a></li>
        <li class="menu-item menu-item-项目"><a href="/projects/" rel="section"><i class="fa fa-satellite fa-fw"></i>项目</a></li>
        <li class="menu-item menu-item-图床"><a href="http://img.liukairui.me/" rel="noopener" target="_blank"><i class="fa fa-bed fa-fw"></i>图床</a></li>
        <li class="menu-item menu-item-云ide"><a href="http://vsc.liukairui.me/" rel="noopener" target="_blank"><i class="fas fa-code fa-fw"></i>云IDE</a></li>
        <li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li>
        <li class="menu-item menu-item-邮箱"><a href="http://mail.liukairui.me/mail" rel="noopener" target="_blank"><i class="fas fa-envelope-open-text fa-fw"></i>邮箱</a></li>
        <li class="menu-item menu-item-rss"><a href="/atom.xml" rel="section"><i class="fa fa-rss fa-fw"></i>RSS</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</div>
        
  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>

  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#ahonoka%E5%92%8C%E6%A0%BC%E7%82%B9%E4%B8%89%E8%A7%92%E5%BD%A2"><span class="nav-number">1.</span> <span class="nav-text">A:honoka和格点三角形</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#bkotori%E5%92%8Cbangdream"><span class="nav-number">2.</span> <span class="nav-text">B:kotori和bangdream</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#cumi%E5%92%8C%E5%BC%93%E9%81%93"><span class="nav-number">3.</span> <span class="nav-text">C:umi和弓道</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#dhanayo%E5%92%8C%E7%B1%B3%E9%A5%AD"><span class="nav-number">4.</span> <span class="nav-text">D：hanayo和米饭</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#erin%E5%92%8C%E5%BF%AB%E9%80%9F%E8%BF%AD%E4%BB%A3"><span class="nav-number">5.</span> <span class="nav-text">E:rin和快速迭代</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#fmaki%E5%92%8Ctree"><span class="nav-number">6.</span> <span class="nav-text">F:maki和tree</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#geli%E5%92%8C%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">7.</span> <span class="nav-text">G：eli和字符串</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#hnozomi%E5%92%8C%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="nav-number">8.</span> <span class="nav-text">H：nozomi和字符串</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#inico%E5%92%8Cniconiconi"><span class="nav-number">9.</span> <span class="nav-text">I：nico和niconiconi</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#j-us%E7%9A%84%E5%BD%B1%E5%93%8D%E5%8A%9B"><span class="nav-number">10.</span> <span class="nav-text">J u&#39;s的影响力</span></a></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Liu Kairui"
      src="/images/avatar.jpg">
  <p class="site-author-name" itemprop="name">Liu Kairui</p>
  <div class="site-description" itemprop="description">LiuKairui Persional Website</div>
</div>
<div class="site-state-wrap site-overview-item animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">45</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">24</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">53</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author site-overview-item animated">
      <span class="links-of-author-item">
        <a href="https://github.com/KairuiLiu" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;KairuiLiu" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:tclkr@live.com" title="E-Mail → mailto:tclkr@live.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://qm.qq.com/cgi-bin/qm/qr?k=oaf3ToOlN17hr5sHV98bT8qxsNYGaw5L&noverify=0" title="QQ → https:&#x2F;&#x2F;qm.qq.com&#x2F;cgi-bin&#x2F;qm&#x2F;qr?k&#x3D;oaf3ToOlN17hr5sHV98bT8qxsNYGaw5L&amp;noverify&#x3D;0" rel="noopener" target="_blank"><i class="fab fa-qq fa-fw"></i>QQ</a>
      </span>
      <span class="links-of-author-item">
        <a href="/atom.xml" title="RSS → &#x2F;atom.xml"><i class="fa fa-rss fa-fw"></i>RSS</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://liukairui.blog.csdn.net/" title="CSDN → https:&#x2F;&#x2F;liukairui.blog.csdn.net" rel="noopener" target="_blank"><i class="fab fa-cuttlefish fa-fw"></i>CSDN</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://liukairui.cc/" title="国内站点 → http:&#x2F;&#x2F;liukairui.cc" rel="noopener" target="_blank"><i class="fa fa-globe fa-fw"></i>国内站点</a>
      </span>
  </div>
  <div class="cc-license site-overview-item animated" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" class="cc-opacity" rel="noopener" target="_blank"><img src="https://cdnjs.cloudflare.com/ajax/libs/creativecommons-vocabulary/2020.11.3/assets/license_badges/small/by_nc_sa.svg" alt="Creative Commons"></a>
  </div>


  <div class="links-of-blogroll site-overview-item animated">
    <div class="links-of-blogroll-title"><i class="fa fa-link fa-fw"></i>
      友情链接
    </div>
    <ul class="links-of-blogroll-list">
        <li class="links-of-blogroll-item">
          <a href="https://paste.ubuntu.com/" title="https:&#x2F;&#x2F;paste.ubuntu.com&#x2F;" rel="noopener" target="_blank">Ubuntu Pastebin</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://send.firefox.com/" title="https:&#x2F;&#x2F;send.firefox.com&#x2F;" rel="noopener" target="_blank">Firefox Send</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://jkwzs.cn/" title="https:&#x2F;&#x2F;jkwzs.cn&#x2F;" rel="noopener" target="_blank">南花醉笔丶の个人博客</a>
        </li>
        <li class="links-of-blogroll-item">
          <a href="https://ywrby.cn/" title="https:&#x2F;&#x2F;ywrby.cn&#x2F;" rel="noopener" target="_blank">Ywrby个人博客</a>
        </li>
    </ul>
  </div>

        </div>
      </div>
    </div>
  </aside>
  <div class="sidebar-dimmer"></div>


    </header>

    
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>
  <div class="reading-progress-bar"></div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.jpg">
      <meta itemprop="name" content="Liu Kairui">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LiuKairui Website">
      <meta itemprop="description" content="LiuKairui Persional Website">
    </span>
    
    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="2020牛客寒假算法基础集训营1题解 | LiuKairui Website">
      <meta itemprop="description" content="原题来自2020牛客寒假算法基础集训营1，作以存档备查">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          2020牛客寒假算法基础集训营1题解
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2020-10-31 00:00:02" itemprop="dateCreated datePublished" datetime="2020-10-31T00:00:02+08:00">2020-10-31</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
        </span>
          ，
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95/%E9%A2%98%E8%A7%A3/" itemprop="url" rel="index"><span itemprop="name">题解</span></a>
        </span>
    </span>

  
    <span id="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/" class="post-meta-item leancloud_visitors" data-flag-title="2020牛客寒假算法基础集训营1题解" title="阅读次数">
      <span class="post-meta-item-icon">
        <i class="far fa-eye"></i>
      </span>
      <span class="post-meta-item-text">阅读次数：</span>
      <span class="leancloud-visitors-count"></span>
    </span>
  
  <span class="post-meta-item">
    
    <span class="post-meta-item-icon">
      <i class="far fa-comment"></i>
    </span>
    <span class="post-meta-item-text">Valine：</span>
  
    <a title="valine" href="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

<script>
    CONFIG.hostname = location.hostname;
</script>
    <span class="post-meta-break"></span>
    <span class="post-meta-item" title="本文字数">
      <span class="post-meta-item-icon">
        <i class="far fa-file-word"></i>
      </span>
      <span class="post-meta-item-text">本文字数：</span>
      <span>10k</span>
    </span>
    <span class="post-meta-item" title="阅读时长">
      <span class="post-meta-item-icon">
        <i class="far fa-clock"></i>
      </span>
      <span class="post-meta-item-text">阅读时长 &asymp;</span>
      <span>9 分钟</span>
    </span>
</div>

            <div class="post-description">原题来自2020牛客寒假算法基础集训营1，作以存档备查</div>
        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
        <h2 id="ahonoka和格点三角形">A:honoka和格点三角形</h2>
<p><img
src="https://img-blog.csdnimg.cn/2020030213101524.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70" />
<strong>输入描述:</strong> 两个正整数和（ <span class="math inline">\(2\
≤n,m≤10^9\)</span>）（<span class="math inline">\(2 ≤n,m≤10^9\)</span>）
<strong>输出描述</strong>: 面积为1的格点三角形的数量，对 <span
class="math inline">\(10^9+7\)</span>取模的结果。 <strong>示例1</strong>
输入</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">2</span> <span class="token number">3</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">6</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">格点如下：
<span class="token operator">*</span>  <span class="token operator">*</span>  <span class="token operator">*</span>
<span class="token operator">*</span>  <span class="token operator">*</span>  <span class="token operator">*</span>
不妨设左下角坐标为<span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">)</span>，右上角坐标为到<span class="token punctuation">(</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">)</span>。
那么三点坐标可选：
（<span class="token number">1</span>，<span class="token number">1</span>）（<span class="token number">1</span>，<span class="token number">2</span>）（<span class="token number">3</span>，<span class="token number">1</span>）
（<span class="token number">1</span>，<span class="token number">1</span>）（<span class="token number">1</span>，<span class="token number">2</span>）（<span class="token number">3</span>，<span class="token number">2</span>）
（<span class="token number">1</span>，<span class="token number">1</span>）（<span class="token number">2</span>，<span class="token number">2</span>）（<span class="token number">3</span>，<span class="token number">1</span>）
（<span class="token number">1</span>，<span class="token number">1</span>）（<span class="token number">3</span>，<span class="token number">1</span>）（<span class="token number">3</span>，<span class="token number">2</span>）
（<span class="token number">1</span>，<span class="token number">2</span>）（<span class="token number">2</span>，<span class="token number">1</span>）（<span class="token number">3</span>，<span class="token number">2</span>）
（<span class="token number">1</span>，<span class="token number">2</span>）（<span class="token number">3</span>，<span class="token number">1</span>）（<span class="token number">3</span>，<span class="token number">2</span>）
所以共有<span class="token number">6</span>个。</code></pre>
<p><strong>示例2</strong> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">100</span> <span class="token number">100</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">7683984</span></code></pre>
<hr />
<p>就是一个分类讨论，据说有公式，不是特别清楚，注意多加()%mod ，玄学mod
代码</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">long</span> <span class="token keyword">long</span> mod<span class="token operator">=</span><span class="token number">1000000007</span><span class="token punctuation">;</span>
<span class="token keyword">long</span> <span class="token keyword">long</span> n<span class="token punctuation">,</span>m<span class="token punctuation">,</span>ans<span class="token punctuation">;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    cin<span class="token operator">>></span>n<span class="token operator">>></span>m<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>m<span class="token operator">>=</span><span class="token number">3</span><span class="token operator">&amp;&amp;</span>n<span class="token operator">>=</span><span class="token number">2</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">+</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>m<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token number">4</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>m<span class="token operator">>=</span><span class="token number">3</span><span class="token operator">&amp;&amp;</span>n<span class="token operator">>=</span><span class="token number">2</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">+</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span>m<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>m<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token number">2</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>m<span class="token operator">>=</span><span class="token number">2</span><span class="token operator">&amp;&amp;</span>n<span class="token operator">>=</span><span class="token number">3</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">+</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>m<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token number">2</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">>=</span><span class="token number">3</span><span class="token operator">&amp;&amp;</span>m<span class="token operator">>=</span><span class="token number">2</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">+</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token number">4</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">>=</span><span class="token number">3</span><span class="token operator">&amp;&amp;</span>m<span class="token operator">>=</span><span class="token number">2</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">+</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token number">2</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">>=</span><span class="token number">2</span><span class="token operator">&amp;&amp;</span>m<span class="token operator">>=</span><span class="token number">3</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token punctuation">(</span>ans<span class="token operator">+</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>m<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">*</span><span class="token number">2</span><span class="token operator">%</span>mod<span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>

    cout<span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="bkotori和bangdream">B:kotori和bangdream</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200302131130492.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>示例1</strong>
<strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">100</span> <span class="token number">50</span> <span class="token number">500</span> <span class="token number">400</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">45000.00</span></code></pre>
<hr />
<p>二项分布数学期望 代码</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
 
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">double</span> n<span class="token punctuation">,</span>x<span class="token punctuation">,</span>a<span class="token punctuation">,</span>b<span class="token punctuation">;</span>
    cin<span class="token operator">>></span>n<span class="token operator">>></span>x<span class="token operator">>></span>a<span class="token operator">>></span>b<span class="token punctuation">;</span>
    <span class="token keyword">double</span> ans<span class="token operator">=</span><span class="token punctuation">(</span>n<span class="token operator">*</span>x<span class="token operator">/</span><span class="token number">100</span><span class="token operator">*</span>a<span class="token operator">+</span>n<span class="token operator">*</span><span class="token punctuation">(</span><span class="token number">100</span><span class="token operator">-</span>x<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">100</span><span class="token operator">*</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%.2f"</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="cumi和弓道">C:umi和弓道</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200302110232288.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1</span> <span class="token number">1</span>
<span class="token number">2</span> <span class="token number">0</span>
<span class="token operator">-</span><span class="token number">1</span> <span class="token number">2</span>
<span class="token operator">-</span><span class="token number">2</span> <span class="token number">1</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">0.50000000</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">umi要保证能射中的靶子不超过<span class="token number">0</span>个，即全部挡住。在y轴上选区间<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">1.5</span><span class="token punctuation">]</span>放置一个长度为<span class="token number">0.5</span>的挡板即可。</code></pre>
<hr />
<p><strong>cout不会尽可能多的显示double位，所以使用printf</strong>
<strong>思路：</strong> 首先统计每一条路径与ox，oy的焦点
然后使用<strong>双指针</strong>对于ox,oy进行求解</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;set></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">double</span> pos_y<span class="token punctuation">[</span><span class="token number">100050</span><span class="token punctuation">]</span><span class="token punctuation">,</span>pos_x<span class="token punctuation">[</span><span class="token number">100050</span><span class="token punctuation">]</span><span class="token punctuation">,</span>x_0<span class="token punctuation">,</span>y_0<span class="token punctuation">;</span>     <span class="token comment">//y轴上点的位置,x轴上点的位置,x0,y0</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span>k<span class="token punctuation">,</span>curx<span class="token punctuation">,</span>cury<span class="token punctuation">;</span>                              <span class="token comment">//n,k,x轴上点的数目,y轴上点的数目</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    cin<span class="token operator">>></span>x_0<span class="token operator">>></span>y_0<span class="token operator">>></span>n<span class="token operator">>></span>k<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">double</span> x<span class="token punctuation">,</span>y<span class="token punctuation">;</span>                             <span class="token comment">//输入x y</span>
        cin<span class="token operator">>></span>x<span class="token operator">>></span>y<span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>x_0<span class="token operator">*</span>x<span class="token operator">></span><span class="token number">0</span><span class="token operator">&amp;&amp;</span>y<span class="token operator">*</span>y_0<span class="token operator">></span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span><span class="token keyword">continue</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>         <span class="token comment">//同象限跳过</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>x_0<span class="token operator">*</span>x<span class="token operator">></span><span class="token number">0</span><span class="token operator">&amp;&amp;</span>x<span class="token operator">==</span>x_0<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>pos_x<span class="token punctuation">[</span>curx<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>x<span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;"    at x= "&lt;&lt; x&lt;&lt;endl;&#125;  //不同象限垂直于ox</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>y_0<span class="token operator">*</span>y<span class="token operator">></span><span class="token number">0</span><span class="token operator">&amp;&amp;</span>y<span class="token operator">==</span>y_0<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>pos_y<span class="token punctuation">[</span>cury<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>y<span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;"    at y= "&lt;&lt; y&lt;&lt;endl;&#125;  //不同象限垂直于oy</span>
        <span class="token keyword">else</span><span class="token punctuation">&#123;</span>
            <span class="token keyword">double</span> yy<span class="token operator">=</span><span class="token punctuation">(</span>y<span class="token operator">-</span>y_0<span class="token punctuation">)</span><span class="token operator">/</span><span class="token punctuation">(</span>x<span class="token operator">-</span>x_0<span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span><span class="token operator">-</span>x_0<span class="token punctuation">)</span><span class="token operator">+</span>y_0 <span class="token punctuation">,</span> xx<span class="token operator">=</span><span class="token punctuation">(</span>x<span class="token operator">-</span>x_0<span class="token punctuation">)</span><span class="token operator">/</span><span class="token punctuation">(</span>y<span class="token operator">-</span>y_0<span class="token punctuation">)</span><span class="token operator">*</span><span class="token punctuation">(</span><span class="token operator">-</span>y_0<span class="token punctuation">)</span><span class="token operator">+</span>x_0<span class="token punctuation">;</span>   <span class="token comment">//直线与ox,oy交点,如果交点在两点间则计入</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>yy<span class="token operator">></span><span class="token function">min</span><span class="token punctuation">(</span>y<span class="token punctuation">,</span>y_0<span class="token punctuation">)</span><span class="token operator">&amp;&amp;</span>yy<span class="token operator">&lt;</span><span class="token function">max</span><span class="token punctuation">(</span>y<span class="token punctuation">,</span>y_0<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>pos_y<span class="token punctuation">[</span>cury<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>yy<span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;"    at y= "&lt;&lt;yy&lt;&lt;endl;&#125;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>xx<span class="token operator">></span><span class="token function">min</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>x_0<span class="token punctuation">)</span><span class="token operator">&amp;&amp;</span>xx<span class="token operator">&lt;</span><span class="token function">max</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span>x_0<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>pos_x<span class="token punctuation">[</span>curx<span class="token operator">++</span><span class="token punctuation">]</span><span class="token operator">=</span>xx<span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;"    at x= "&lt;&lt;xx&lt;&lt;endl;&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token function">sort</span><span class="token punctuation">(</span>pos_y<span class="token punctuation">,</span>pos_y<span class="token operator">+</span>cury<span class="token punctuation">)</span><span class="token punctuation">;</span>                         <span class="token comment">//排序做双指针</span>
    <span class="token function">sort</span><span class="token punctuation">(</span>pos_x<span class="token punctuation">,</span>pos_x<span class="token operator">+</span>curx<span class="token punctuation">)</span><span class="token punctuation">;</span>
    cury<span class="token operator">=</span><span class="token function">unique</span><span class="token punctuation">(</span>pos_y<span class="token punctuation">,</span>pos_y<span class="token operator">+</span>cury<span class="token punctuation">)</span><span class="token operator">-</span>pos_y<span class="token punctuation">;</span>            <span class="token comment">//排除的在oy上重复的点 如:x0=1 y0=1 &#123;x=3 y=-1&#125;与&#123;x=4 y=-2&#125; 在ox上均为(2,0)此时应去重</span>
    curx<span class="token operator">=</span><span class="token function">unique</span><span class="token punctuation">(</span>pos_x<span class="token punctuation">,</span>pos_x<span class="token operator">+</span>curx<span class="token punctuation">)</span><span class="token operator">-</span>pos_x<span class="token punctuation">;</span>

    <span class="token keyword">int</span> global<span class="token operator">=</span>n<span class="token operator">-</span>k<span class="token punctuation">;</span>
    <span class="token keyword">double</span> ans<span class="token operator">=</span><span class="token number">0x3f3f3f3f</span><span class="token punctuation">;</span>                      <span class="token comment">//初始化答案</span>

    <span class="token keyword">if</span><span class="token punctuation">(</span>cury<span class="token operator">>=</span>global<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>                           <span class="token comment">//oy上有足够多的点被选择</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">+</span>global<span class="token operator">-</span><span class="token number">1</span><span class="token operator">&lt;</span>cury<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>     <span class="token comment">//滑动窗口</span>
            ans<span class="token operator">=</span><span class="token function">min</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span>pos_y<span class="token punctuation">[</span>i<span class="token operator">+</span>global<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span>pos_y<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token comment">//process ox</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>curx<span class="token operator">>=</span>global<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">+</span>global<span class="token operator">-</span><span class="token number">1</span><span class="token operator">&lt;</span>curx<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            ans<span class="token operator">=</span><span class="token function">min</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span>pos_x<span class="token punctuation">[</span>i<span class="token operator">+</span>global<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span>pos_x<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>

    <span class="token keyword">if</span><span class="token punctuation">(</span>ans<span class="token operator">!=</span><span class="token number">0x3f3f3f3f</span><span class="token punctuation">)</span><span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%.8f"</span><span class="token punctuation">,</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">else</span> <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"-1"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="dhanayo和米饭">D：hanayo和米饭</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200302110652420.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span>
<span class="token number">2</span> <span class="token number">5</span> <span class="token number">1</span> <span class="token number">3</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">4</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">开始共有<span class="token number">5</span>个碗，每个碗内分别有<span class="token number">1</span>、<span class="token number">2</span>、<span class="token number">3</span>、<span class="token number">4</span>、<span class="token number">5</span>粒米饭。rin拿走的是第四碗。这么简单的样例连tairitsu都看得懂好伐<span class="token operator">~</span></code></pre>
<hr />
<p>大水题</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
 
<span class="token keyword">int</span> date<span class="token punctuation">[</span><span class="token number">100050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
 
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> n<span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>date<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">sort</span><span class="token punctuation">(</span>date<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>date<span class="token operator">+</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>date<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">!=</span>i<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>cout<span class="token operator">&lt;&lt;</span>i<span class="token punctuation">;</span><span class="token keyword">break</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="erin和快速迭代">E:rin和快速迭代</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200302110905806.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> 输入</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">12</span></code></pre>
<p>输出</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">4</span></code></pre>
<p>说明</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">12</span>的因子：<span class="token number">1</span>，<span class="token number">2</span>，<span class="token number">3</span>，<span class="token number">4</span>，<span class="token number">6</span>，<span class="token number">12</span>。共<span class="token number">6</span>个。
<span class="token number">6</span>的因子：<span class="token number">1</span>，<span class="token number">2</span>，<span class="token number">3</span>，<span class="token number">6</span>。共<span class="token number">4</span>个。
<span class="token number">4</span>的因子：<span class="token number">1</span>，<span class="token number">2</span>，<span class="token number">4</span>。共<span class="token number">3</span>个。
<span class="token number">3</span>的因子：<span class="token number">1</span>，<span class="token number">3</span>。共<span class="token number">2</span>个。
<span class="token number">12</span> → <span class="token number">6</span> → <span class="token number">4</span> → <span class="token number">3</span> → <span class="token number">2</span> ， 故迭代了<span class="token number">4</span>次。</code></pre>
<hr />
<p>签到题</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
 
<span class="token keyword">long</span> <span class="token keyword">long</span> x<span class="token punctuation">,</span>times<span class="token punctuation">;</span>
 
<span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">get_num</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span> t<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>i<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">*</span>i<span class="token operator">&lt;=</span>t<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>t<span class="token operator">%</span>i<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>ans<span class="token operator">++</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    i<span class="token operator">--</span><span class="token punctuation">;</span>
    ans<span class="token operator">*=</span><span class="token number">2</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">*</span>i<span class="token operator">==</span>t<span class="token punctuation">)</span>ans<span class="token operator">--</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
 
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> n<span class="token punctuation">;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> num<span class="token punctuation">;</span>
    cin<span class="token operator">>></span>n<span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        times<span class="token operator">++</span><span class="token punctuation">;</span>
        num<span class="token operator">=</span><span class="token function">get_num</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>num<span class="token operator">==</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token keyword">break</span><span class="token punctuation">;</span>
        n<span class="token operator">=</span>num<span class="token punctuation">;</span>
        <span class="token comment">// cout&lt;&lt;num&lt;&lt;"**\n";</span>
    <span class="token punctuation">&#125;</span>
    cout<span class="token operator">&lt;&lt;</span>times<span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="fmaki和tree">F:maki和tree</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200302111039787.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span>
WBW
<span class="token number">1</span> <span class="token number">2</span>
<span class="token number">2</span> <span class="token number">3</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">树表示如下：</code></pre>
<p><img
src="https://img-blog.csdnimg.cn/2020030211121019.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <pre class="language-cpp" data-language="cpp"><code class="language-cpp">其中只有<span class="token number">2</span>号是黑色点。
<span class="token operator">&lt;</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token operator">></span>、<span class="token operator">&lt;</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token operator">></span>、<span class="token operator">&lt;</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token operator">></span>三种取法都只经过一个黑色点。</code></pre></p>
<hr />
<p>这个题，分类讨论只有两种情况</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">1.</span> 纯白链<span class="token operator">-</span>黑点<span class="token operator">-</span>纯白链
<span class="token number">2.</span> 纯白链<span class="token operator">-</span>黑点</code></pre>
<p>所以枚举每一个黑点，先找出他附近所有纯白链的个数就是2的答案，然后两两组合就是1的答案，这里可以直接使用并查集染色确定每一条纯白块并统计数量，其中的纯白链个数就是块元素个数，然后维护前缀和(不是数组，只是记录前缀和)加速1的运算</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">const</span> <span class="token keyword">int</span> MAX_N<span class="token operator">=</span><span class="token number">10000050</span><span class="token punctuation">;</span>                                                   <span class="token comment">//写正确数据范围只过11%qwq</span>
<span class="token keyword">struct</span> <span class="token class-name">edge</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> v<span class="token punctuation">,</span>next<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>E<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> p<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">,</span>dad<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">,</span>eid<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>num<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">,</span>n<span class="token punctuation">;</span>
<span class="token keyword">char</span> s<span class="token punctuation">[</span>MAX_N<span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">getdad</span><span class="token punctuation">(</span><span class="token keyword">int</span> p<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>                                                   <span class="token comment">//并查集</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>dad<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token operator">==</span>p<span class="token punctuation">)</span><span class="token keyword">return</span> p<span class="token punctuation">;</span>
    <span class="token keyword">return</span> dad<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">getdad</span><span class="token punctuation">(</span>dad<span class="token punctuation">[</span>p<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">insert</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">,</span><span class="token keyword">int</span> v<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    E<span class="token punctuation">[</span>eid<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token operator">=</span>p<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token punctuation">;</span>
    E<span class="token punctuation">[</span>eid<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token operator">=</span>v<span class="token punctuation">;</span>
    p<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token operator">=</span>eid<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">insert2</span><span class="token punctuation">(</span><span class="token keyword">int</span> u<span class="token punctuation">,</span><span class="token keyword">int</span> v<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">insert</span><span class="token punctuation">(</span>u<span class="token punctuation">,</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">insert</span><span class="token punctuation">(</span>v<span class="token punctuation">,</span>u<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>u<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'W'</span><span class="token operator">&amp;&amp;</span>s<span class="token punctuation">[</span>v<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'W'</span><span class="token operator">&amp;&amp;</span><span class="token function">getdad</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span><span class="token operator">!=</span><span class="token function">getdad</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token punctuation">)</span>dad<span class="token punctuation">[</span><span class="token function">getdad</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">getdad</span><span class="token punctuation">(</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>         <span class="token comment">//并查集合并</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">void</span> <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>                                                                <span class="token comment">//初始化</span>
    <span class="token function">memset</span><span class="token punctuation">(</span>p<span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>p<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    eid<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>dad<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>i<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token function">get_ans</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">long</span> <span class="token keyword">long</span> ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token keyword">if</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'W'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>                                     <span class="token comment">//统计并查集内节点数目</span>
        num<span class="token punctuation">[</span><span class="token function">getdad</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'B'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>                                                      <span class="token comment">//找黑色</span>
            <span class="token keyword">int</span> cur<span class="token operator">=</span>p<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token keyword">long</span> <span class="token keyword">long</span> sgm<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>                                                <span class="token comment">//前缀和</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span>cur<span class="token operator">+</span><span class="token number">1</span><span class="token operator">&amp;&amp;</span>s<span class="token punctuation">[</span>E<span class="token punctuation">[</span>cur<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'B'</span><span class="token punctuation">)</span>cur<span class="token operator">=</span>E<span class="token punctuation">[</span>cur<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token punctuation">;</span>                  <span class="token comment">//找到黑色节点连接的第一个白节点</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span>cur<span class="token operator">==</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token keyword">continue</span><span class="token punctuation">;</span>                                            <span class="token comment">//一个白节点都没有退出</span>
            sgm<span class="token operator">=</span>num<span class="token punctuation">[</span><span class="token function">getdad</span><span class="token punctuation">(</span>E<span class="token punctuation">[</span>cur<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">;</span>                                      <span class="token comment">//第一个白节点所在并查集节点数直接放并查集</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span>cur<span class="token operator">=</span>E<span class="token punctuation">[</span>cur<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token punctuation">;</span>cur<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>cur<span class="token operator">=</span>E<span class="token punctuation">[</span>cur<span class="token punctuation">]</span><span class="token punctuation">.</span>next<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>                     <span class="token comment">//继续往后找</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>E<span class="token punctuation">[</span>cur<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'B'</span><span class="token punctuation">)</span><span class="token keyword">continue</span><span class="token punctuation">;</span>                               <span class="token comment">//如果这个是黑色就找下一个白色的</span>
                ans<span class="token operator">+=</span>num<span class="token punctuation">[</span><span class="token function">getdad</span><span class="token punctuation">(</span>E<span class="token punctuation">[</span>cur<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token operator">*</span>sgm<span class="token punctuation">;</span>                             <span class="token comment">//第一张情况</span>
                sgm<span class="token operator">+=</span>num<span class="token punctuation">[</span><span class="token function">getdad</span><span class="token punctuation">(</span>E<span class="token punctuation">[</span>cur<span class="token punctuation">]</span><span class="token punctuation">.</span>v<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">;</span>                                 <span class="token comment">//维护前缀和</span>
            <span class="token punctuation">&#125;</span>
            ans<span class="token operator">+=</span>sgm<span class="token punctuation">;</span>                                                       <span class="token comment">//第二种情况</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> ans<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">init</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%s"</span><span class="token punctuation">,</span>s<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> u<span class="token punctuation">,</span>v<span class="token punctuation">;</span>
        <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>u<span class="token punctuation">,</span><span class="token operator">&amp;</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">insert2</span><span class="token punctuation">(</span>u<span class="token punctuation">,</span>v<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    cout<span class="token operator">&lt;&lt;</span><span class="token function">get_ans</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="geli和字符串">G：eli和字符串</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200302120123472.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span> <span class="token number">2</span>
abeba</code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">选择“beb”子串，长度为<span class="token number">3</span>，其中包含相同的两个<span class="token char">'b'</span></code></pre>
<hr />
<p>查找最小子串满足某条件，我想到二分长度
考虑jduge函数：这个子串定义和我们平时不一样，他只能去除头尾，所以上一个双指针结束</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
 
<span class="token keyword">char</span> ss<span class="token punctuation">[</span><span class="token number">200500</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span>k<span class="token punctuation">,</span>times<span class="token punctuation">[</span><span class="token number">500</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
 
<span class="token keyword">bool</span> <span class="token function">init</span><span class="token punctuation">(</span><span class="token keyword">int</span> len<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">memset</span><span class="token punctuation">(</span>times<span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>times<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>len<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">++</span>times<span class="token punctuation">[</span>ss<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token char">'a'</span><span class="token punctuation">]</span><span class="token operator">>=</span>k<span class="token punctuation">)</span><span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
 
<span class="token keyword">bool</span> <span class="token function">scoll</span><span class="token punctuation">(</span><span class="token keyword">int</span> len<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">init</span><span class="token punctuation">(</span>len<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">+</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token operator">&lt;</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token operator">--</span>times<span class="token punctuation">[</span>ss<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span><span class="token char">'a'</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">++</span>times<span class="token punctuation">[</span>ss<span class="token punctuation">[</span>i<span class="token operator">+</span>len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">-</span><span class="token char">'a'</span><span class="token punctuation">]</span><span class="token operator">>=</span>k<span class="token punctuation">)</span><span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
 
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">,</span><span class="token operator">&amp;</span>k<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%s"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>ss<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">int</span> l<span class="token operator">=</span>k<span class="token punctuation">,</span>r<span class="token operator">=</span>n<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span><span class="token function">init</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>cout<span class="token operator">&lt;&lt;</span><span class="token string">"-1"</span><span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>l<span class="token operator">&lt;</span>r<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">int</span> mid<span class="token operator">=</span><span class="token punctuation">(</span>l<span class="token operator">+</span>r<span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">scoll</span><span class="token punctuation">(</span>mid<span class="token punctuation">)</span><span class="token punctuation">)</span>r<span class="token operator">=</span>mid<span class="token punctuation">;</span>
        <span class="token keyword">else</span> l<span class="token operator">=</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    cout<span class="token operator">&lt;&lt;</span>l<span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="hnozomi和字符串">H：nozomi和字符串</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200302120850152.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">5</span> <span class="token number">1</span>
<span class="token number">10101</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">3</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp">只有 <span class="token number">1</span> 次操作机会。
将第二个位置的 <span class="token number">0</span> 改成 <span class="token number">1</span> ，字符串变成 <span class="token number">11101</span>，可以选出 <span class="token number">111</span>子串，长度为<span class="token number">3</span> 。
如果修改第三个或者第四个位置的字符也可以选出长度为 <span class="token number">3</span> 的子串。</code></pre>
<hr />
<p>又是一个二分双指针?????
于是把前一题代码改了下就交了，<code>TLE</code> 考虑特殊性质， -
首先我发现这个序列<strong>仅有</strong> 0/1 <strong>两个数字</strong>
这是一个01序列，所以
<strong>我们只需要求它的前缀和就可以得到0-n有多少个1！</strong>
<strong>然后长度-1的数字就知道了0的长度</strong> 这是一种方法 -
我发现他只有两种字符，我们可以直接计算前n个数中有几个1,0</p>
<p>对于一个位置cur，我们有四个情况情况
这个位置是1，我们只想把后面的0-&gt;1
这个位置是1，我们只想把后面的1-&gt;0
这个位置是0，我们只想把后面的0-&gt;1
这个位置是0，我们只想把后面的1-&gt;0 我们只讨论第一个情况 我们
<strong>定</strong> cur为这个我选的序列的第一个
我们获取这个点钱的一，因为我们是往后找k个0-&gt;1
所以我想找一个点，这个点他的前缀0-开始点前缀0==k，而且我想要这个点尽可能大
<strong>用upper_bounder!</strong> 然后这题就水过去了</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cmath></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;algorithm></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name function">max</span><span class="token expression"><span class="token punctuation">(</span>x<span class="token punctuation">,</span>y<span class="token punctuation">)</span> x<span class="token operator">></span>y<span class="token operator">?</span>x<span class="token operator">:</span>y</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
 
<span class="token keyword">char</span> ss<span class="token punctuation">[</span><span class="token number">200050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> n<span class="token punctuation">,</span>k<span class="token punctuation">,</span>num0<span class="token punctuation">[</span><span class="token number">200050</span><span class="token punctuation">]</span><span class="token punctuation">,</span>num1<span class="token punctuation">[</span><span class="token number">200050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
 
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d%s"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">,</span><span class="token operator">&amp;</span>k<span class="token punctuation">,</span>ss<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
     
    <span class="token comment">// build the sigma '1'&amp;'0'</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'0'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>num0<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>num0<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>num1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>num1<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'1'</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>num1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>num1<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>num0<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>num0<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
 
    <span class="token keyword">long</span> <span class="token keyword">long</span> <span class="token keyword">int</span> ans<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
 
    <span class="token comment">// 1->0</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'0'</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">upper_bound</span><span class="token punctuation">(</span>num1<span class="token operator">+</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num1<span class="token operator">+</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+</span>k<span class="token punctuation">)</span><span class="token operator">-</span>num1<span class="token operator">-</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'1'</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">upper_bound</span><span class="token punctuation">(</span>num1<span class="token operator">+</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num1<span class="token operator">+</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num1<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+</span>k<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">-</span>num1<span class="token operator">-</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
 
    <span class="token comment">// 0->1</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'1'</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">upper_bound</span><span class="token punctuation">(</span>num0<span class="token operator">+</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num0<span class="token operator">+</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num0<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+</span>k<span class="token punctuation">)</span><span class="token operator">-</span>num0<span class="token operator">-</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>ss<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span><span class="token char">'0'</span><span class="token punctuation">)</span>ans<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span><span class="token function">upper_bound</span><span class="token punctuation">(</span>num0<span class="token operator">+</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num0<span class="token operator">+</span>n<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>num0<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+</span>k<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">-</span>num0<span class="token operator">-</span>i<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
 
    cout<span class="token operator">&lt;&lt;</span>ans<span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="inico和niconiconi">I：nico和niconiconi</h2>
<figure>
<img
src="https://img-blog.csdnimg.cn/20200302125312277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" />
<figcaption aria-hidden="true">在这里插入图片描述</figcaption>
</figure>
<p><strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">19</span> <span class="token number">1</span> <span class="token number">2</span> <span class="token number">5</span>
niconiconiconiconi<span class="token operator">~</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">7</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token string">"niconi"</span>co<span class="token string">"niconiconi"</span><span class="token operator">~</span>
故为<span class="token number">2</span><span class="token operator">+</span><span class="token number">5</span><span class="token operator">=</span><span class="token number">7</span>分</code></pre>
<hr />
<p>无后效性，dp... 情况1 : dp[i]=max(dp[i],dp[i-4]+a) 情况2 :
dp[i]=max(dp[i],dp[i-6]+b) 情况3 : dp[i]=max(dp[i],dp[i-10]+c)
代码：</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;iostream></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstdio></span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span> <span class="token string">&lt;cstring></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token keyword">long</span> <span class="token keyword">long</span> dp<span class="token punctuation">[</span><span class="token number">300050</span><span class="token punctuation">]</span><span class="token punctuation">,</span>n<span class="token punctuation">,</span>a<span class="token punctuation">,</span>b<span class="token punctuation">,</span>c<span class="token punctuation">;</span>
<span class="token keyword">char</span> ss<span class="token punctuation">[</span><span class="token number">300050</span><span class="token punctuation">]</span><span class="token punctuation">;</span>

<span class="token keyword">bool</span> <span class="token function">my_cmp</span><span class="token punctuation">(</span>string t<span class="token punctuation">,</span><span class="token keyword">int</span> cur<span class="token punctuation">,</span><span class="token keyword">int</span> len<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>len<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>t<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">!=</span>ss<span class="token punctuation">[</span>cur<span class="token operator">-</span>len<span class="token operator">+</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d%d%d%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>n<span class="token punctuation">,</span><span class="token operator">&amp;</span>a<span class="token punctuation">,</span><span class="token operator">&amp;</span>b<span class="token punctuation">,</span><span class="token operator">&amp;</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%s"</span><span class="token punctuation">,</span>ss<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>n<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">></span><span class="token number">3</span><span class="token punctuation">)</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">my_cmp</span><span class="token punctuation">(</span><span class="token string">"nico"</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">4</span><span class="token punctuation">]</span><span class="token operator">+</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;"*";&#125;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">></span><span class="token number">5</span><span class="token punctuation">)</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">my_cmp</span><span class="token punctuation">(</span><span class="token string">"niconi"</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">6</span><span class="token punctuation">]</span><span class="token operator">+</span>b<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;"&amp;";&#125;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>i<span class="token operator">></span><span class="token number">9</span><span class="token punctuation">)</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">my_cmp</span><span class="token punctuation">(</span><span class="token string">"niconiconi"</span><span class="token punctuation">,</span>i<span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token operator">-</span><span class="token number">10</span><span class="token punctuation">]</span><span class="token operator">+</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span><span class="token comment">//cout&lt;&lt;"^";&#125;</span>
        
    <span class="token punctuation">&#125;</span>
    cout<span class="token operator">&lt;&lt;</span>dp<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
    <span class="token comment">// for(int i=1;i&lt;=n;i++)cout&lt;&lt;dp[i]&lt;&lt;" * ";</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<hr />
<h2 id="j-us的影响力">J u's的影响力</h2>
<p><img
src="https://img-blog.csdnimg.cn/20200302130144686.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> <strong>输入</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">4</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">2</span> <span class="token number">1</span></code></pre>
<p><strong>输出</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token number">72</span></code></pre>
<p><strong>说明</strong></p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token function">f</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">=</span><span class="token number">2</span>，<span class="token function">f</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token operator">=</span><span class="token number">3</span>，<span class="token function">f</span><span class="token punctuation">(</span><span class="token number">3</span><span class="token punctuation">)</span><span class="token operator">=</span><span class="token function">f</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token function">f</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token number">2</span><span class="token operator">=</span><span class="token number">12</span>，<span class="token function">f</span><span class="token punctuation">(</span><span class="token number">4</span><span class="token punctuation">)</span><span class="token operator">=</span><span class="token function">f</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token function">f</span><span class="token punctuation">(</span><span class="token number">3</span><span class="token punctuation">)</span><span class="token operator">*</span><span class="token number">2</span><span class="token operator">=</span><span class="token number">72</span></code></pre>
<hr />
<p>非常明显，可以用Fib(i),Fib(i-1),Fib(i-2)轻松表示出i&gt;=4的式子
然后我想： Fib求大数太慢了，于是用cmath的sqrt用fib通项公式计算
<del>然后用快速幂加速</del> 不行，快速幂处理小数无法取模qwq
<del>用内置的pow</del> 内置pow有效位数<strong>太差</strong>
那看来只能用递推公式了 但是实在是<strong>太慢了!!</strong>
这时只能使用矩阵快速幂这个东西 <img
src="https://img-blog.csdnimg.cn/20200302132422518.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xpdWthaXJ1aQ==,size_16,color_FFFFFF,t_70"
alt="在这里插入图片描述" /> （看这个博文吧qwq） 完事</p>
<pre class="language-cpp" data-language="cpp"><code class="language-cpp"><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h></span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">define</span> <span class="token macro-name">ll</span> <span class="token expression"><span class="token keyword">long</span> <span class="token keyword">long</span></span></span>
<span class="token keyword">struct</span> <span class="token class-name">mt</span><span class="token punctuation">&#123;</span>
    ll a<span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span><span class="token punctuation">;</span>
mt <span class="token function">t</span><span class="token punctuation">(</span>mt a<span class="token punctuation">,</span>mt b<span class="token punctuation">,</span>ll mod<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    mt res<span class="token punctuation">;</span>
    <span class="token keyword">int</span> i<span class="token punctuation">,</span>j<span class="token punctuation">,</span>k<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">3</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span><span class="token number">3</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            res<span class="token punctuation">.</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span>k<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>k<span class="token operator">&lt;</span><span class="token number">3</span><span class="token punctuation">;</span>k<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
                res<span class="token punctuation">.</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+=</span>a<span class="token punctuation">.</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">*</span>b<span class="token punctuation">.</span>a<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
                res<span class="token punctuation">.</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">%=</span>mod<span class="token punctuation">;</span>
            <span class="token punctuation">&#125;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
mt <span class="token function">power</span><span class="token punctuation">(</span>mt a<span class="token punctuation">,</span>ll b<span class="token punctuation">,</span>ll mod<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    mt res<span class="token punctuation">;</span>
    <span class="token keyword">int</span> i<span class="token punctuation">,</span>j<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">3</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span><span class="token number">3</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            res<span class="token punctuation">.</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    res<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span>res<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>res<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
 
    <span class="token keyword">while</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>b<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span>res<span class="token operator">=</span><span class="token function">t</span><span class="token punctuation">(</span>res<span class="token punctuation">,</span>a<span class="token punctuation">,</span>mod<span class="token punctuation">)</span><span class="token punctuation">;</span>
        b<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
        a<span class="token operator">=</span><span class="token function">t</span><span class="token punctuation">(</span>a<span class="token punctuation">,</span>a<span class="token punctuation">,</span>mod<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
ll <span class="token function">feb</span><span class="token punctuation">(</span>ll n<span class="token punctuation">,</span>ll mod<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    mt temp<span class="token punctuation">;</span>
    <span class="token keyword">int</span> i<span class="token punctuation">,</span>j<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">3</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span><span class="token number">3</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span>temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    mt res<span class="token operator">=</span><span class="token function">power</span><span class="token punctuation">(</span>temp<span class="token punctuation">,</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span>mod<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token punctuation">(</span>res<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">+</span>res<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
ll <span class="token function">feb2</span><span class="token punctuation">(</span>ll n<span class="token punctuation">,</span>ll mod<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    mt temp<span class="token punctuation">;</span>
    <span class="token keyword">int</span> i<span class="token punctuation">,</span>j<span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span>i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span><span class="token number">3</span><span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span>j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span><span class="token number">3</span><span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
            temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">&#125;</span>
    <span class="token punctuation">&#125;</span>
    temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">=</span>temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span>temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">=</span>temp<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
    mt res<span class="token operator">=</span><span class="token function">power</span><span class="token punctuation">(</span>temp<span class="token punctuation">,</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span>mod<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token punctuation">(</span>res<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">2</span><span class="token operator">*</span>res<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span>res<span class="token punctuation">.</span>a<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">%</span>mod<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
ll <span class="token function">power</span><span class="token punctuation">(</span>ll a<span class="token punctuation">,</span>ll b<span class="token punctuation">,</span>ll mod<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    ll res<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">;</span>
 
    <span class="token keyword">while</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>b<span class="token operator">&amp;</span><span class="token number">1</span><span class="token punctuation">)</span>res<span class="token operator">=</span>res<span class="token operator">*</span>a<span class="token operator">%</span>mod<span class="token punctuation">;</span>
        b<span class="token operator">>>=</span><span class="token number">1</span><span class="token punctuation">;</span>
        a<span class="token operator">=</span>a<span class="token operator">*</span>a<span class="token operator">%</span>mod<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>
    <span class="token keyword">int</span> m<span class="token operator">=</span><span class="token number">1e9</span><span class="token operator">+</span><span class="token number">7</span><span class="token punctuation">;</span>
 
    <span class="token keyword">int</span> i<span class="token punctuation">,</span>j<span class="token punctuation">;</span>
    ll n<span class="token punctuation">,</span>x<span class="token punctuation">,</span>y<span class="token punctuation">,</span>a<span class="token punctuation">,</span>b<span class="token punctuation">;</span>
    cin<span class="token operator">>></span>n<span class="token operator">>></span>x<span class="token operator">>></span>y<span class="token operator">>></span>a<span class="token operator">>></span>b<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">==</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>cout<span class="token operator">&lt;&lt;</span>x<span class="token operator">%</span>m<span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>n<span class="token operator">==</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>cout<span class="token operator">&lt;&lt;</span>y<span class="token operator">%</span>m<span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>x<span class="token operator">%</span>m<span class="token operator">==</span><span class="token number">0</span><span class="token operator">||</span>y<span class="token operator">%</span>m<span class="token operator">==</span><span class="token number">0</span><span class="token operator">||</span>a<span class="token operator">%</span>m<span class="token operator">==</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">&#123;</span>cout<span class="token operator">&lt;&lt;</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span><span class="token punctuation">&#125;</span>
    x<span class="token operator">%=</span>m<span class="token punctuation">;</span>
    y<span class="token operator">%=</span>m<span class="token punctuation">;</span>
 
    a<span class="token operator">=</span><span class="token function">power</span><span class="token punctuation">(</span>a<span class="token operator">%</span>m<span class="token punctuation">,</span>b<span class="token punctuation">,</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>       <span class="token comment">//这里要注意a对m取模</span>
     
    cout<span class="token operator">&lt;&lt;</span><span class="token function">power</span><span class="token punctuation">(</span>x<span class="token punctuation">,</span><span class="token function">feb</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">,</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">,</span>m<span class="token punctuation">)</span><span class="token operator">*</span><span class="token function">power</span><span class="token punctuation">(</span>y<span class="token punctuation">,</span><span class="token function">feb</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">,</span>m<span class="token punctuation">)</span><span class="token operator">%</span>m<span class="token operator">*</span><span class="token function">power</span><span class="token punctuation">(</span>a<span class="token operator">%</span>m<span class="token punctuation">,</span><span class="token function">feb2</span><span class="token punctuation">(</span>n<span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">,</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">%</span><span class="token punctuation">(</span>m<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">,</span>m<span class="token punctuation">)</span><span class="token operator">%</span>m<span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
 
<span class="token punctuation">&#125;</span></code></pre>

    </div>

    
    
    
      


    <footer class="post-footer">
          <div class="reward-container">
  <div></div>
  <button>
    赞赏
  </button>
  <div class="post-reward">
      <div>
        <img src="/images/wechatpay.png" alt="Liu Kairui 微信">
        <span>微信</span>
      </div>
      <div>
        <img src="/images/alipay.png" alt="Liu Kairui 支付宝">
        <span>支付宝</span>
      </div>

  </div>
</div>

          

<div class="post-copyright">
<ul>
  <li class="post-copyright-author">
      <strong>本文作者： </strong>Liu Kairui
  </li>
  <li class="post-copyright-link">
      <strong>本文链接：</strong>
      <a href="http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/" title="2020牛客寒假算法基础集训营1题解">http://liukairui.me/article/2020牛客寒假算法基础集训营1题解/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" rel="noopener" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>

          <div class="post-tags">
              <a href="/tags/%E7%AE%97%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> 算法</a>
              <a href="/tags/%E7%89%9B%E5%AE%A2/" rel="tag"><i class="fa fa-tag"></i> 牛客</a>
              <a href="/tags/ACM/" rel="tag"><i class="fa fa-tag"></i> ACM</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/article/vscode%E9%85%8D%E7%BD%AE%E7%AC%94%E8%AE%B0(%E7%8E%AF%E5%A2%83%E9%85%8D%E7%BD%AE,%E6%8F%92%E4%BB%B6%E6%8E%A8%E8%8D%90,%E7%BE%8E%E5%8C%96)(C++,Python,LaTeX,R...)/" rel="prev" title="vscode配置笔记(环境配置,插件推荐,美化)(C++,Python,LaTeX,R...)">
                  <i class="fa fa-chevron-left"></i> vscode配置笔记(环境配置,插件推荐,美化)(C++,Python,LaTeX,R...)
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/article/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E5%8F%8C%E6%8C%87%E9%92%88(%E5%B0%BA%E5%8F%96%E6%B3%95)/" rel="next" title="数据结构-双指针(尺取法)">
                  数据结构-双指针(尺取法) <i class="fa fa-chevron-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments" id="valine-comments"></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 2019 – 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Liu Kairui</span>
</div>
<div class="busuanzi-count">
    <span class="post-meta-item" id="busuanzi_container_site_uv">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-item" id="busuanzi_container_site_pv">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" rel="noopener" target="_blank">NexT.Muse</a> 强力驱动
  </div>
  <div class="addthis_inline_share_toolbox">
    <script src="//s7.addthis.com/js/300/addthis_widget.js#pubid=ra-6231eb6f709fc868" async="async"></script>
  </div><script
  async
  src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"
></script>

 
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/moment.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment-precise-range-plugin@1.3.0/moment-precise-range.min.js"></script>
<script>
  function timer() {
    var ages = moment.preciseDiff(moment(),moment(20201101,"YYYYMMDD"));
    ages = ages.replace(/years?/, "年");
    ages = ages.replace(/months?/, "月");
    ages = ages.replace(/days?/, "天");
    ages = ages.replace(/hours?/, "小时");
    ages = ages.replace(/minutes?/, "分");
    ages = ages.replace(/seconds?/, "秒");
    ages = ages.replace(/\d+/g, '<span class="daysCnt" style="color:#1890ff">$&</span>');
    div.innerHTML = `我已在此等候你 ${ages}`;
    div.className="workDays";
  }
  var div = document.createElement("div");
  //插入到copyright之后
  var copyright = document.querySelector(".copyright");
  document.querySelector(".footer-inner").insertBefore(div, copyright.nextSibling);
  timer();
  setInterval("timer()",1000)
</script>



    </div>
  </footer>

  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/@next-theme/pjax@0.5.0/pjax.min.js" integrity="sha256-3NkoLDrmHLTYj7csHIZSr0MHAFTXth7Ua/DDt4MRUAg=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/fancybox/3.5.7/jquery.fancybox.min.js" integrity="sha256-yt2kYMy0w8AbtF89WXb2P1rfjcP/HTHLT7097U8Y5b8=" crossorigin="anonymous"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/lozad.js/1.16.0/lozad.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/pangu/4.0.7/pangu.min.js"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  
<script src="https://cdn.jsdelivr.net/npm/hexo-generator-searchdb@1.4.0/dist/search.js" integrity="sha256-vXZMYLEqsROAXkEw93GGIvaB2ab+QW6w3+1ahD9nXXA=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>


  <script class="next-config" data-name="mermaid" type="application/json">{"enable":true,"theme":"forest","js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mermaid/8.14.0/mermaid.min.js","integrity":"sha256-7wT34TI0pEBeEFoi4z+vhuSddGh6vUTMWdqJ2SDe2jg="}}</script>
  <script src="/js/third-party/tags/mermaid.js"></script>

  <script src="/js/third-party/fancybox.js"></script>

  <script src="/js/third-party/pace.js"></script>

  
  <script data-pjax async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>


  <script class="next-config" data-name="leancloud_visitors" type="application/json">{"enable":true,"app_id":"ABKlVtS4cyaWYEwunPyK3sXt-9Nh9j0Va","app_key":"xxGXdTTEGEVifs2TLB35844I","server_url":"https://abklvts4.lc-cn-e1-shared.com","security":false}</script>
  <script src="/js/third-party/statistics/lean-analytics.js"></script>


  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","mhchem":true,"js":{"url":"https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.0/es5/tex-mml-chtml.min.js"}}</script>
<script src="/js/third-party/math/mathjax.js"></script>


  <script src="https://cdnjs.cloudflare.com/ajax/libs/quicklink/2.2.0/quicklink.umd.js" integrity="sha256-4kQf9z5ntdQrzsBC3YSHnEz02Z9C1UeW/E9OgnvlzSY=" crossorigin="anonymous"></script>
  <script class="next-config" data-name="quicklink" type="application/json">{"enable":true,"home":false,"archive":false,"delay":true,"timeout":3000,"priority":true,"url":"http://liukairui.me/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/"}</script>
  <script src="/js/third-party/quicklink.js"></script>
<script src="https://cdn.jsdelivr.net/npm/darkmode-js@1.5.7/lib/darkmode-js.min.js"></script>

<script>
var options = {
  bottom: '64px',
  right: 'unset',
  left: '32px',
  time: '0.5s',
  mixColor: 'transparent',
  backgroundColor: 'transparent',
  buttonColorDark: '#100f2c',
  buttonColorLight: '#fff',
  saveInCookies: true,
  label: '🌓',
  autoMatchOsTheme: true
}
const darkmode = new Darkmode(options);
window.darkmode = darkmode;
darkmode.showWidget();
</script>


<script class="next-config" data-name="valine" type="application/json">{"enable":true,"appId":"ABKlVtS4cyaWYEwunPyK3sXt-9Nh9j0Va","appKey":"xxGXdTTEGEVifs2TLB35844I","serverURLs":"https://abklvts4.lc-cn-e1-shared.com","placeholder":"请开始你的表演","avatar":"identicon","meta":["nick","mail","link"],"pageSize":10,"lang":"zh-CN","visitor":false,"comment_count":true,"recordIP":true,"enableQQ":true,"requiredFields":[],"el":"#valine-comments","path":"/article/2020%E7%89%9B%E5%AE%A2%E5%AF%92%E5%81%87%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%E9%9B%86%E8%AE%AD%E8%90%A51%E9%A2%98%E8%A7%A3/"}</script>
<script>
document.addEventListener('page:loaded', () => {
  NexT.utils.loadComments(CONFIG.valine.el)
    .then(() => NexT.utils.getScript(
      'https://cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js',
      { condition: window.Valine }
    ))
    .then(() => {
      new Valine(CONFIG.valine);
    });
});
</script>


  <script async src="/js/fireworks.js"></script>




  <script src="/js/activate-power-mode.min.js"></script>
  <script>
    POWERMODE.colorful = true;
    POWERMODE.shake = false;
    document.body.addEventListener('input', POWERMODE);
  </script>




  <script src="/js/wobblewindow.js"></script>
  <script>
    //只在桌面版网页启用特效 记得同步到header.njk
    if( window.innerWidth > 768  ){
      $(document).ready(function () {
        
          $('body>main>header').wobbleWindow({
            radius: 50,
            movementTop: false,
            movementLeft: false,
            movementRight: false,
            debug: false,
          });
        

        //
        //  $('body header>aside').wobbleWindow({
        //    radius: 50,
        //    movementLeft: false,
        //    movementTop: false,
        //    movementBottom: false,
        //    position: 'fixed',
        //    debug: false,
        //  });
        //

        
          $('body>footer').wobbleWindow({
            radius: 50,
            movementBottom: false,
            movementLeft: false,
            movementRight: false,
            debug: false,
          });
        
      });
    }
  </script>


 
<script>
  $(document).ready(function(){
    var beian = document.querySelector(".footer-inner > .beian > a");
    var cpr=document.querySelector(".footer-inner > .copyright");
    var cnz=document.querySelector(".workDays");//.parentNode;
    var bsz=document.querySelector(".busuanzi-count");
    if(cnz!=null&&bsz!=null)
      cnz.parentNode.insertBefore(bsz,cnz);
    if(bsz == null || bsz == undefined || document.querySelector("#busuanzi_value_site_pv").innerText=="" || document.querySelector("#busuanzi_value_site_uv").innerText == "")
      bsz.remove();
    checkIndex();
    if(beian){cpr.classList.add('split-line');cpr.appendChild(beian);}
  })
  $(document).on('pjax:complete',checkIndex);
</script>



<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"log":false,"model":{"jsonPath":"/live2dw/assets/hijiki.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false},"react":{"opacity":0.7}});</script></body>
</html>
